303. 区域和检索 - 数组不可变

#leetcode/prefix-sum

303. 区域和检索 - 数组不可变

Solution Tips

其实前缀和经常用于对数组做预处理，将题目做等价转化成求 preSum 的问题

降低查询时的时间复杂度。在处理子数组求和时很好用。

结合题意要求，有时候甚至不用求出 preSum 数组的每一项

因为我们可能根本不关心 preSum 们对应了具体哪一项 nums[i]

可能我们只关心出现过哪些 preSum ，我是联想到《560 题.和为 K 的子数组》了

方案一: 暴力法

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.nums = nums;
};

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    let res = 0;
    for (let i = left; i <= right; i++) {
        res += this.nums[i];
    }
    return res;
};

时间复杂度 O(n)，看起来挺好，存在什么问题？

如果 sumRange 方法被反复调用，每次都是 O(n)，「查询」的代价有点大

方案二: 前缀和

var NumArray = function(nums) {
    const n = nums.length;
    this.sums = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        this.sums[i + 1] = this.sums[i] + nums[i];
    }
};

NumArray.prototype.sumRange = function(i, j) {
    return this.sums[j + 1] - this.sums[i];
};

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.sums = new Array(nums.length).fill(0);
    this.sums[0] = nums[0]
    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        this.sums[i] = this.sums[i-1] + num
    }
};

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    // left 为 0 时, 减 0 就行
    console.log('this.sums[right]: ', this.sums[right]);
    console.log('this.sums[left - 1]: ', this.sums[left - 1]);
    return this.sums[right] - (this.sums[left - 1] || 0)
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
*/
var obj = new NumArray([-2, 0, 3, -5, 2, -1])
var param_1 = obj.sumRange(0,2)
console.log('param_1: ', param_1);

设置 this.sums[-1] = 0 我觉得更好理解

303. 区域和检索 - 数组不可变

Similar Question

Solution Tips

方案一: 暴力法

方案二: 前缀和